import com.kiwi.nixu.common.LNode;

/**
 * 题目描述：
 * 把链表相邻元素翻转，如给定链表为1→2→3→4→5→6→7，
 * 则翻转后的链表变为2→1→4→3→6→5→7。
 */
public class G如何把链表相邻元素翻转 {

    /**
     * 方法二：
     * 就地逆序主要思路：通过调整结点指针域的指向来直接调换相邻的两个结点。
     * 如果单链表恰好有偶数个结点，那么只需要将奇偶结点对调即可，
     * 如果链表有奇数个结点，那么只需要将除最后一个结点外的其他结点进行奇偶对调即可。
     * 为了便于理解，下图给出了其中第一对结点对调的方法
     * 在上图中，当前遍历到结点cur，
     * 通过步骤（1）～（6）用虚线的指针来代替实线的指针实现相邻结点的逆序。
     * 其中，步骤（1）～（4）实现了前两个结点的逆序操作，
     * 步骤（5）和（6）向后移动指针，
     * 接着可以采用同样的方式实现后面两个相邻结点的逆序操作。实现代码如下
     */

    public static void reverse2(LNode head) {
        if (head == null || head.next == null) {
            return;
        }
        LNode cur = head.next;
        LNode pre = head;
        LNode next = null;
        while (cur != null && cur.next != null) {
            next = cur.next.next;
            pre.next = cur.next;
            cur.next.next = cur;
            cur.next = next;
            pre = cur;
            cur = next;
        }
    }

    public static void main(String[] args) {
        int i = 1;
        LNode head = new LNode();
        head.next = null;
        LNode tmp = null;
        LNode cur = head;
        for (; i < 8; i++) {
            tmp = new LNode();
            tmp.data = i;
            tmp.next = null;
            cur.next = tmp;
            cur = tmp;
        }
        System.out.println("顺序输出：");
        for (cur = head.next; cur != null; cur = cur.next) {
            System.out.print(cur.data + "");
        }
        reverse2(head);
        System.out.println("逆序输出：");
        for (cur = head.next; cur != null; cur = cur.next) {
            System.out.print(cur.data + "");
        }
        for (cur = head.next; cur != null; ) {
            cur = cur.next;
        }

    }
}
